package org.xingole.daily;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href="https://leetcode.com/problems/power-grid-maintenance/description/">
 * 3607 Problem Description
 * </a>
 * 
 * @since 2025-11-6
 */
public class PowerGridMaintenance {

    static class DSU {

        private int[] parent;

        public DSU(int size) {
            parent = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            return parent[x] == x ? x : (parent[x] = find(parent[x]));
        }

        public void join(int u, int v) {
            parent[find(v)] = find(u);
        }

    }

    public int[] processQueries1(int c, int[][] connections, int[][] queries) {
        /*
         * Approach 1: Union-Find + Reverse Processing Query
         * 
         * 1. Calculate connected components
         * 
         * Use the Union-Find data structure to calculate connected components. Merge
         * nodes that have a connected relationship, then use the root node of each set
         * as a handle for the connected component. Subsequently, the query operation of
         * the Union-Find structure can quickly determine which connected component a
         * particular node belongs to.
         * 
         * 2. Maintaining the minimum identifier of the currently online power stations
         * 
         * Consider processing the queries in reverse order. From this perspective, an
         * offline operation effectively becomes an online operation. As each power
         * plant comes back online, maintaing the minimum identifier among all online
         * power plants simply requires repeatedly taking the min and update it.
         * 
         */
        DSU dsu = new DSU(c + 1);

        for (int[] p : connections) {
            dsu.join(p[0], p[1]);
        }

        boolean[] online = new boolean[c + 1];
        // For each power plant i, we can count the number of times it is taken offline,
        // denoted as offlineCounts[i]. During the reverse processing of the queries, every
        // time we encounter an offline operation, we decrement the corresponding
        // offlineCount[i] by one. When a power plant s satisfies offlineCounts[i] = 1,
        // it indicates that this is the moment when the power plant was first taken offline
        // in the original order of operations.
        int[] offlineCounts = new int[c + 1];
        Arrays.fill(online, true);
        Map<Integer, Integer> minimumOnlineStations = new HashMap<>();
        for (int[] q : queries) {
            int op = q[0];
            int x  = q[1];
            if (op == 2) {
                online[x] = false;
                offlineCounts[x]++;
            }
        }

        for (int i = 1; i <= c; i++) {
            int root = dsu.find(i);
            if (!minimumOnlineStations.containsKey(root)) {
                minimumOnlineStations.put(root, -1);
            }

            int station = minimumOnlineStations.get(root);
            if (online[i]) {
                if (station == -1 || station > i) {
                    minimumOnlineStations.put(root, i);
                }
            }
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = queries.length - 1; i >= 0; i--) {
            int op = queries[i][0];
            int x  = queries[i][1];
            int root = dsu.find(x);
            int station = minimumOnlineStations.get(root);

            if (op == 1) {
                if (online[x]) {
                    ans.add(x);
                } else {
                    ans.add(station);
                }
            }

            if (op == 2) {
                if (offlineCounts[x] > 1) {
                    offlineCounts[x]--;
                } else {
                    online[x] = true;
                    if (station == -1 || station > x) {
                        minimumOnlineStations.put(root, x);
                    }
                }
            }
        }

        Collections.reverse(ans);
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}
